//一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出
//这个数字。 
//
// 
//
// 示例 1: 
//
// 输入: [0,1,3]
//输出: 2
// 
//
// 示例 2: 
//
// 输入: [0,1,2,3,4,5,6,7,9]
//输出: 8 
//
// 
//
// 限制： 
//
// 1 <= 数组长度 <= 10000 
// Related Topics 数组 二分查找 
// 👍 36 👎 0

package leetcode.editor.cn;
//Java：0～n-1中缺失的数字
public class QueShiDeShuZiLcof{
    public static void main(String[] args) {
        Solution solution = new QueShiDeShuZiLcof().new Solution();
        System.out.println(solution.missingNumber(new int[]{0,1,2,3,4,5,6,7,9})) ;
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
        public int missingNumber(int[] nums) {
            /**
             将数组的下标作为字典
             对于每个数字应该 nums[i] == i  把每个元素交换到下标为nums[i]处
             0 1 3 4

             */
            if(nums==null||nums.length<=0){
                return -1;
            }
            int len=nums.length;
            for(int i=0;i<len;i++){
                if(i!=nums[i]) {
                    if(nums[i]>=0&&nums[i]<len) {//注意这里范围的判断
                        nums[nums[i]] = nums[i];
                    }
                }
            }
            for(int i=0;i<len;i++){
                if(nums[i]!=i){
                    return i;
                }
            }
            return len;//注意返回的结果，如果全部有序的话返回的便是数组的长度
        }
}
//leetcode submit region end(Prohibit modification and deletion)

}
